package com.sicheng.lc.周赛.分类.哈西表or计数or滑动窗口or双指针;

import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/8 22:47
 */
public class 统计坏数对的数目 {
    // j - i != nums[j] - nums[i]
    // nums[i] - i != nums[j] - j
    // 使用数组a[i] = nums[i] - i
    // 就转化成求取 a[i]!=a[j]的 (i,j)对
    // 实际上  a[i]==a[j] 的(i,j)对更好求， 再求个补集就是坏数对的个数
    // 以上分析过程不需要真的开一个a数组来存储,只是方便分析问题...我们把nums跑一遍就行
    public long countBadPairs(int[] nums) {
        int n = nums.length;
        // 所有数对 C(n,2)
        long c = (long) (n - 1) * n >> 1;
        long t = 0;
        HashMap<Integer, Integer> cnt = new HashMap<>(10000);
        // 求好数对 a[i]==a[j] 的个数
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i] - i;
            int y = cnt.getOrDefault(x, 0);
            t += y;
            cnt.put(x, y + 1);
        }

        return c - t;


    }
}
